SWERC 2013 H Binary Tree

发表于 | 更新于 | 分类于 ， ， | 阅读次数：
本文字数： 2.3k | 阅读时长 ≈ 2 分钟

task

众所周知，二叉树是一种最多含有2个子节点的树形数据结构。
现在有一棵无限大的二叉树。在这棵树中，每个节点都有左右两个儿子，和一个父亲。我们称根节点的父亲是它自己。kxj极其无聊地将手指指向根节点，然后极其无聊地根据指令S移动手指。
一串指令S为一个字符串，这个字符串是包含大写的L,R,U分别表示着走向当前节点的左儿子，右儿子和父亲。
现在kxj又得到了另一串指令L，这一串指令从指令S结束时手指所在的节点开始移动。但是这一次kxj可以跳掉T中的任意指令(可能一个都不跳，或者全跳)。kxj想知道最终他的手指可以指向多少个不同的节点。
S,T的长度<=100000

solution

首先我们将指令S处理一下，因为在这一条指令中是有许多无效操作，即‘U’操作，每次遇到一个‘U’就意味着往上走，那么我们可以发现我们又退回到上一个点了，那么这之间的操作都是无效的。这样我们最后处理完的指令中只有L和R，这一条指令就在二叉树中构成一条向下的路径。
那么接下来我们考虑在每个深度向下走，在初始深度我们可以使用T中的所有的L和R，用这些L和R构成的不同子序列都代表着一个不同的结果。而当我们每用一个‘U’，我们都可以上去一层(root除外)，这时候我们只能往另一个儿子那边走，即如果初始点是一个左儿子，那么我们我们在我们可以用的L和R中找所有一个R开头的不同的子序列。
所以其实题目就变成了在一个只有L和R的字符串中找到所有不同的子序列。
对于这种题，我们可以借用trie树的思路，trie树上有几个节点就代表有多少的子序列。
而trie树中为R的节点都代表着一个以R结尾的字符串。L同理。
所以我们就枚举指令T，每次将trie树中一个与当前字符有关的字符串删去，然后遇到一个‘U’，就将加上此时trie树中的‘L’节点或者‘R’节点。
但是有一个非常严肃的问题，我们无法做到在trie树上删点。
那么根据通常的思路我们改删点为加点即可，倒着枚举指令T，然后我们就可以将每个非‘U’的字符加到当前trie树上的节点上(前提是该节点的儿子中没有这种字符)。
而且实际上我们没有必要将trie数构出来，因为我们只是想知道trie树中L和R节点的个数而已。所以我们只要维护5个参数L，R，Lcnt，Rcnt，leaf 就好了。
L和R分别表示trie树中L节点和R节点的个数，Lcnt和Rcnt分别表示在trie树中有多少节点是只有一个右儿子(即左儿子是空的)或只有一个左儿子(即右儿子是空的)，leaf就是叶子节点。
每当我们枚举到一个‘L’，那么此时trie树上就有leaf+Lcnt个节点可以加一个左儿子。那么几个参数的更新如下：
$L+=leaf+Lcnt$
$Rcnt+=leaf$
$leaf+=Lcnt$
$Lcnt=0$
枚举到‘R’同理。
如果枚举到‘U’呢？假设这是正数第x个‘U’，那么我们就要看在新的S指令中的正数第x个字符什么，如果是‘L’，那么我们就为答案加上一个R+1,反之同理。
但是当x大于S中字符的个数是，我们不用更新答案。
最后我们还要加上一个$L+R+1$，表示在初始节点时向下走的方案数。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <cstdio>
#include <cstring>
#include <algorithm>
#define M 100005
#define P 21092013
using namespace std;
char S[M],T[M];
void Mod(int &a,int b){
	a+=b;
	if(a>=P)a-=P;
}
int main(){
	int cas,o=0;
	scanf("%d",&cas);
	while(cas--&&scanf("%s %s",&S,&T)){
		int n=strlen(S);
		int m=strlen(T);
		int L=0,R=0,t=0,Lcnt=0,Rcnt=0,leaf=1,ans=0;
		for(int i=0;i<n;i++)
			if(t&&S[i]=='U')t--;
			else S[t++]=S[i];
		n=t;t=0;
		for(int i=0;i<m;i++)t+=(T[i]=='U');
		t=n-t;
		for(int i=m-1;i>=0;i--){
			if(T[i]=='L'){
				Mod(L,leaf);
				Mod(L,Lcnt);
				Mod(Rcnt,leaf);
				Mod(leaf,Lcnt);
				Lcnt=0;
			}
			else if(T[i]=='R'){
				Mod(R,leaf);
				Mod(R,Rcnt);
				Mod(Lcnt,leaf);
				Mod(leaf,Rcnt);
				Rcnt=0;
			}
			else if(t<n){
				t++;
				if(t<=0)continue;
				if(S[t-1]=='L')Mod(ans,(R+1)%P);
				else Mod(ans,(L+1)%P);
				
			}
		}
		Mod(ans,(L+R+1)%P);
		printf("Case %d: %d\n",++o,ans);
	}
	return 0;
}